General purpose microprocessor and Digital Signal Processors ("DSP") are well known in the art. Many software algorithms employed on general purpose microprocessor systems use a series of software logical operations to perform bitwise data manipulations, such as a series of read, rotate, XOR, and write instructions. DSP software algorithms to perform discrete transforms such as Fast Fourier Transforms ("FFT") are also well known. In order to conserve memory, which reduces system size, power consumption, and cost, most discrete transforms are executed "in-place" using the same memory area to store to algorithm output as the memory area where the input values are stored.
FIG. 1 shows a simplified butterfly signal flow graph which requires only one complex multiplication, a method commonly used in discrete transform software algorithms. FIG. 2 shows a flow graph of an eight-point Discrete Fourier Transform ("DFT"), in which a problem with in-place execution of such algorithms is evident. If a decimation-in-time ("DIT") decomposition is used by an algorithm, the input data must be stored non-sequentially in linear memory such that the actual memory address where each input data is stored is a "bit reversed" address value of their normal sequential address in order for the algorithm output data to be in sequence in memory. For example, note that input x(4) in FIG. 2 is stored in the second memory address. If one converts the data index of the data value, 4 in this case, to binary, b'100, and performs a bit reversal on that binary value, which is b'001 in this case, the proper "bit reversed" input address is found, which is "1" in base 10. For a further example, note that input x(6), which has a binary index value of b'110, is actually input to the algorithm at memory location b'011, or memory location 3 in base 10.
If an algorithm uses decimation-in-frequency ("DIF") decomposition, the converse is true about the order of the input and output data: input data is input to the algorithm in normal sequential order, and output data is yielded in "bit reversed" non-sequential order.
These phenomena of discrete transforms performed in-place are well known within the art. Many software algorithms and methods have been proposed and used to bit reverse indices into tables, to use look up tables to quickly perform index bit reversal, and to minimize the number of DSP processor cycles needed to resequence input and output data. However, the prior art software algorithm methods incur multiple DSP processor cycles, thereby reducing the effective calculation capability of the DSP. For further understanding of this subject, one could refer to:
(a) "Digital Signal Processing" by Alan V. Oppenheim and Ronald W. Schafer, Prentic-Hall Press, published in 1975; and PA1 (b) "Bit-Reverse and Digit-Reverse: Linear-Time Small Lookup Table Implementation for the TMS320C6000", Application Report: SPRA440, by Chad Courtney, Texas Instruments Incorporated, published in May, 1998.
Further, algorithms which use floating point math operations commonly store floating point data in two components, the fractional component or "mantissa", and the radix power or "exponent". If a given processing system is equipped with 16-bit wide data memory, and the floating point math uses the Institute of Electrical and Electronic Engineers ("IEEE") standard 32-bit format having a 23-bit precision on the mantissa and an 8-bit precision on the exponent plus a 1-bit sign, it may be desirable to compress the exponent and mantissa by means of bit extraction and concatenation, into a single 15-bit value such that it can be stored with the sign bit into a single 16-bit wide data memory location. However, this data compression operation when performed in software can require several bitwise extractions, at least one bitwise "OR" operation, followed by a data STORE operation to complete the compression.
Finally, many software algorithms have a requirement to extract a segment or segments of a data word, perform bitwise manipulations such as segment swapping or bit reversing. This requires similar software operations to the compression operation described supra.
Therefore, there exists a need in the art for a system solution to perform data storage order bit reversing without incurring unnecessary CPU calculation cycles in order to maximize the execution throughput of the DSP during discrete Fourier transform operations.
Further, there exists a general need in the processing art to provide a flexible, dynamically reconfigurable bitwise data manipulator to perform bit field and bitwise operations such as bit reversing, bit field extraction, and concatenation.